{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subtree of Another Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree #string-matching #hash-function"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树 #字符串匹配 #哈希函数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSubtree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #另一棵树的子树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>给你两棵二叉树 <code>root</code> 和 <code>subRoot</code> 。检验 <code>root</code> 中是否包含和 <code>subRoot</code> 具有相同结构和节点值的子树。如果存在，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>二叉树 <code>tree</code> 的一棵子树包括 <code>tree</code> 的某个节点和这个节点的所有后代节点。<code>tree</code> 也可以看做它自身的一棵子树。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/28/subtree1-tree.jpg\" style=\"width: 532px; height: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,4,5,1,2], subRoot = [4,1,2]\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/04/28/subtree2-tree.jpg\" style=\"width: 502px; height: 458px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>root</code> 树上的节点数量范围是 <code>[1, 2000]</code></li>\n",
    "\t<li><code>subRoot</code> 树上的节点数量范围是 <code>[1, 1000]</code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= root.val <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> <= subRoot.val <= 10<sup>4</sup></code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subtree-of-another-tree](https://leetcode.cn/problems/subtree-of-another-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subtree-of-another-tree](https://leetcode.cn/problems/subtree-of-another-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,4,5,1,2]\\n[4,1,2]', '[3,4,5,1,2,null,null,null,null,0]\\n[4,1,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        if not subRoot:\n",
    "            return True\n",
    "        if not root:\n",
    "            return False\n",
    "        if self.isSame(root, subRoot):\n",
    "            return True\n",
    "        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)\n",
    "    \n",
    "    \n",
    "    def isSame(self, p, q):\n",
    "        if not p and not q:\n",
    "            return True\n",
    "        if not p and q or not q and p or p.val != q.val:\n",
    "            return False\n",
    "        return self.isSame(p.left, q.left) and self.isSame(p.right, q.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        candidates = []\n",
    "        \n",
    "        stack = []\n",
    "        current = s\n",
    "        while stack or current:\n",
    "            if current is not None:\n",
    "                if current.val == t.val:\n",
    "                    candidates.append(current)\n",
    "                stack.append(current)\n",
    "                current = current.left\n",
    "            else:\n",
    "                current = stack.pop()\n",
    "                current = current.right\n",
    "        \n",
    "        for x in candidates:\n",
    "            stack_a = [x]\n",
    "            stack_b = [t]\n",
    "            level_a = []\n",
    "            level_b = []\n",
    "            flag = True\n",
    "            while stack_a or stack_b:\n",
    "                a, b = stack_a.pop(), stack_b.pop()\n",
    "\n",
    "                if (a is None and b is not None) or (b is None and a is not None) or (a is not None and b is not None and a.val!=b.val):\n",
    "\n",
    "                    flag = False\n",
    "                    break\n",
    "                \n",
    "                if a is not None:\n",
    "                    level_a.append(a.left)\n",
    "                    level_a.append(a.right)\n",
    "                if b is not None:\n",
    "                    level_b.append(b.left)\n",
    "                    level_b.append(b.right)\n",
    "                \n",
    "                if stack_a == [] and level_a != []:\n",
    "                    stack_a += level_a\n",
    "                    level_a = []\n",
    "\n",
    "                if stack_b == [] and level_b != []:\n",
    "                    stack_b += level_b\n",
    "                    level_b = []\n",
    "            if flag:\n",
    "                return True\n",
    "            \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stack = [s]\n",
    "        flag = False\n",
    "        f1 = []\n",
    "        while stack:\n",
    "            ss = stack.pop(0)\n",
    "            if ss.val==t.val:\n",
    "                f1.append(ss)\n",
    "                flag = True\n",
    "            if ss.left:\n",
    "                stack.append(ss.left)\n",
    "            if ss.right:\n",
    "                stack.append(ss.right)\n",
    "        if not flag:\n",
    "            return False\n",
    "        res = []\n",
    "        for i in f1:\n",
    "            stackS = [i]\n",
    "            stackT = [t]\n",
    "            while stackS and stackT:\n",
    "                ss = stackS.pop(0)\n",
    "                tt = stackT.pop(0)\n",
    "                if ss.val!=tt.val:\n",
    "                    res.append(False)\n",
    "                    break\n",
    "                if ss.left and tt.left:\n",
    "                    stackS.append(ss.left)\n",
    "                    stackT.append(tt.left)\n",
    "                if ss.right and tt.right:\n",
    "                    stackS.append(ss.right)\n",
    "                    stackT.append(tt.right)\n",
    "                if (ss.left and not tt.left) or (ss.right and not tt.right) or (\n",
    "                    not ss.left and tt.left) or (not ss.right and tt.right):\n",
    "                    res.append(False)\n",
    "                    break\n",
    "        print(res, f1)\n",
    "        if len(res)!=len(f1):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def equals(s,t):\n",
    "        if(s==None and t==None):\n",
    "            return True\n",
    "        if s==None or t==None:\n",
    "            return False\n",
    "        return s.val==t.val and Solution.equals(s.left,t.left) and Solution.equals(s.right,t.right)\n",
    "    def traverse(s,t):\n",
    "        return s!=None and (Solution.equals(s,t) or Solution.traverse(s.left,t) or Solution.traverse(s.right,t))\n",
    "        \n",
    "        \n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        if s==None and t==None:\n",
    "            return True\n",
    "        \n",
    "        return Solution.traverse(s,t)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # dfs 二叉树子树匹配问题（Same Tree）\n",
    "        if not s:\n",
    "            return False\n",
    "        if self.isSame(s, t):\n",
    "            return True\n",
    "        return self.isSubtree(s.left, t) | self.isSubtree(s.right, t)\n",
    "    def isSame(self, s, t):\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        if s.val != t.val:\n",
    "            return False\n",
    "        return self.isSame(s.left, t.left) & self.isSame(s.right, t.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return self.isSameTree(s,t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)\n",
    "    \n",
    "    \n",
    "    def isSameTree(self, s, t):\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def isSubtree(self, s, t):\n",
    "    #     \"\"\"\n",
    "    #     :type s: TreeNode\n",
    "    #     :type t: TreeNode\n",
    "    #     :rtype: bool\n",
    "    #     \"\"\"\n",
    "    #     # Solution 1:\n",
    "    #     # dfs 二叉树子树匹配问题（转化为Same Tree更好理解）\n",
    "    #     # 这里实际上使用两个递归函数进行判断首先是通过isSubtree逐层向下进行递归，同时通过issanme判断两个子树是否同时满足所有条件，\n",
    "    #     if not s:\n",
    "    #         return False\n",
    "    #     if self.isSame(s, t):\n",
    "    #         return True\n",
    "    #     return self.isSubtree(s.left, t) | self.isSubtree(s.right, t)\n",
    "    # def isSame(self, s, t):\n",
    "    #     if not s and not t:\n",
    "    #         return True\n",
    "    #     if not s or not t:\n",
    "    #         return False\n",
    "    #     if s.val != t.val:\n",
    "    #         return False\n",
    "    #     return self.isSame(s.left, t.left) & self.isSame(s.right, t.right)\n",
    "    \n",
    "        # Solution 2:\n",
    "        # 将二叉树s和二叉树t序列化为字符串，如果二叉树在二叉树s中存在且为子树关系则返回Ture，否则为False\n",
    "    def isSubtree(self, s, t):\n",
    "        sc, tc = [], []\n",
    "        self.serialize(s, sc)\n",
    "        self.serialize(t, tc)\n",
    "        sc = ''.join(sc)\n",
    "        tc = ''.join(tc)\n",
    "        print(tc)\n",
    "        print(sc)\n",
    "        return sc.find(tc) != -1\n",
    "    def serialize(self, node, c):\n",
    "        if not node:\n",
    "            c.append(',#')\n",
    "        else:\n",
    "            c.append(',' + str(node.val))\n",
    "            # c += ',' + str(node.val)\n",
    "            self.serialize(node.left, c)\n",
    "            self.serialize(node.right, c)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        \n",
    "        def cmp2Trees(tree1, tree2):\n",
    "            if not tree1 and not tree2: return True\n",
    "            if (not tree1 and tree2) or (tree1 and not tree2): return False\n",
    "            if tree1.val != tree2.val: return False\n",
    "            return cmp2Trees(tree1.left, tree2.left) and cmp2Trees(tree1.right, tree2.right)\n",
    "        \n",
    "#         def allChild(root):\n",
    "#             if not root: return root\n",
    "#             if not root.left and not root.right: return [[root]]\n",
    "#             lft = allChild(root.left)\n",
    "#             rht = allChild(root.right)\n",
    "#             if not lft:\n",
    "#                 return rht + [[root]]\n",
    "#             if not rht:\n",
    "#                 return lft + [[root]]\n",
    "#             return lft + rht + [[root]]\n",
    "            \n",
    "        \n",
    "#         for x in allChild(s):\n",
    "#             if cmp2Trees(x[0], t): return True\n",
    "            \n",
    "#         return False\n",
    "\n",
    "\n",
    "        def allChild(root):\n",
    "            if not root: return []\n",
    "            if not root.left and not root.right: return [root]\n",
    "            lft = allChild(root.left)\n",
    "            rht = allChild(root.right)\n",
    "            return lft + rht + [root]\n",
    "            \n",
    "        \n",
    "        for x in allChild(s):\n",
    "            if cmp2Trees(x, t): return True\n",
    "            \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 另一种思路，分别将两棵树序列化\n",
    "        # 然后根据序列化的结果判断是否存在子树\n",
    "        s_serialize = self.serialize(s)\n",
    "        t_serialize = self.serialize(t)\n",
    "        \n",
    "        if t_serialize in s_serialize:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    \n",
    "    def serialize(self, root):\n",
    "        if root is None:\n",
    "            return []\n",
    "        \n",
    "        def pre_order(root):\n",
    "            if root:\n",
    "                result.append('^' + str(root.val))\n",
    "                pre_order(root.left)\n",
    "                pre_order(root.right)\n",
    "            else:\n",
    "                result.append('^#')\n",
    "                \n",
    "        result = []\n",
    "        pre_order(root)\n",
    "        \n",
    "        return ','.join(result)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def search(s, t):\n",
    "            if not s: return False\n",
    "            if helper(s, t): return True\n",
    "            else: return search(s.left, t) or search(s.right, t)\n",
    "        \n",
    "        def helper(s, t):\n",
    "            if not s and not t:\n",
    "                return True\n",
    "            elif s and t and s.val == t.val:\n",
    "                return helper(s.left, t.left) and helper(s.right, t.right)\n",
    "            else: \n",
    "                return False\n",
    "        \n",
    "        return search(s, t)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: TreeNode\n",
    "        :type t: TreeNode\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        flag = [False]\n",
    "        def isSub(s,t):\n",
    "            if s:\n",
    "                if s.val == t.val:\n",
    "                    if self.isSame(s,t):\n",
    "                        print(self.isSame(s,t))\n",
    "                        flag[0] = True\n",
    "                isSub(s.left, t)\n",
    "                isSub(s.right, t)\n",
    "        isSub(s,t)\n",
    "        return flag[0]\n",
    "    def isSame(self, s, t):\n",
    "        if s and t:\n",
    "            return s.val == t.val and self.isSame(s.left, t.left) and self.isSame(s.right, t.right)\n",
    "        elif (s and not t) or (t and not s):\n",
    "            print(11111111)\n",
    "            return False\n",
    "        elif not s and not t:\n",
    "            return True\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        stack = [s]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node is not None:\n",
    "                if node.val == t.val:\n",
    "                    stack1 = []\n",
    "                    stack1.append((node.right, t.right))\n",
    "                    stack1.append((node.left, t.left))\n",
    "                    while stack1:\n",
    "                        node1, node2 = stack1.pop()\n",
    "                        if node1 is not None or node2 is not None:\n",
    "                            if node1 is None or node2 is None or node1.val != node2.val:\n",
    "                                break\n",
    "                            else:\n",
    "                                stack1.append((node1.right, node2.right))\n",
    "                                stack1.append((node1.left, node2.left))\n",
    "                        if not stack1:\n",
    "                            return True\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        stack = [s]\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node is not None:\n",
    "                if node.val == t.val:\n",
    "                    stack1 = []\n",
    "                    stack1.append((node.right, t.right))\n",
    "                    stack1.append((node.left, t.left))\n",
    "                    while stack1:\n",
    "                        node1, node2 = stack1.pop()\n",
    "                        if node1 is not None or node2 is not None:\n",
    "                            if node1 is None or node2 is None or node1.val != node2.val:\n",
    "                                break\n",
    "                            else:\n",
    "                                stack1.append((node1.right, node2.right))\n",
    "                                stack1.append((node1.left, node2.left))\n",
    "                        if not stack1:\n",
    "                            return True\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "\n",
    "        def find_t_root(s, t):\n",
    "            stack = []\n",
    "            visited = set()\n",
    "\n",
    "            stack.append(s)\n",
    "\n",
    "            match_root = []\n",
    "\n",
    "            while len(stack) > 0:\n",
    "                ele = stack.pop()\n",
    "                visited.add(ele)\n",
    "\n",
    "                if ele.val == t.val:\n",
    "                    match_root.append(ele)\n",
    "\n",
    "                if ele.left is not None and ele.left not in visited:\n",
    "                    stack.append(ele.left)\n",
    "\n",
    "                if ele.right is not None and ele.right not in visited:\n",
    "                    stack.append(ele.right)\n",
    "            return match_root\n",
    "\n",
    "        def dfs(s):\n",
    "\n",
    "            stack = []\n",
    "            visited = set()\n",
    "            pth = []\n",
    "\n",
    "            stack.append(s)\n",
    "\n",
    "            while len(stack) > 0:\n",
    "                ele = stack.pop()\n",
    "                visited.add(ele)\n",
    "                pth.append(ele.val)\n",
    "\n",
    "                if ele.left is not None and ele.left not in visited:\n",
    "                    stack.append(ele.left)\n",
    "\n",
    "                if ele.right is not None and ele.right not in visited:\n",
    "                    stack.append(ele.right)\n",
    "\n",
    "            return pth\n",
    "\n",
    "\n",
    "        if s == None or t == None:\n",
    "            return False\n",
    "\n",
    "        s_list = find_t_root(s, t)\n",
    "        if s_list == []:\n",
    "            return False\n",
    "        else:\n",
    "\n",
    "            for s in s_list:\n",
    "                s_pth = dfs(s)\n",
    "                t_pth = dfs(t)\n",
    "                if s_pth == t_pth:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        # write code here\n",
    "        if not t:\n",
    "            return False\n",
    "        p1, p2 = self.preorder(s), self.preorder(t)\n",
    "        return True if self.kmp(p1, p2) != -1 else False\n",
    "    \n",
    "    def preorder(self, root):\n",
    "        stack = [root]\n",
    "        res = []\n",
    "        while stack:\n",
    "            cur = stack.pop()\n",
    "            if cur:\n",
    "                res.append(cur.val)\n",
    "                stack.append(cur.right)\n",
    "                stack.append(cur.left)\n",
    "            else:\n",
    "                res.append('#')\n",
    "        return res\n",
    "    \n",
    "    def kmp(self, txt, pat):\n",
    "        if not pat:\n",
    "            return 0\n",
    "        m, n, nxt = len(txt), len(pat), self.getNext(pat)\n",
    "        i, j = 0, 0\n",
    "        while i < m and j < n:\n",
    "            if j == -1 or txt[i] == pat[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j = nxt[j]\n",
    "        return i-j if j == n else -1\n",
    "    \n",
    "    def getNext(self, s):\n",
    "        nxt = [0 for _ in range(len(s))]\n",
    "        nxt[0] = -1\n",
    "        i, j = 0, -1\n",
    "        while i < len(s)-1:\n",
    "            if j == -1 or s[j] == s[i]:\n",
    "                j += 1\n",
    "                i += 1\n",
    "                nxt[i] = j\n",
    "            else:\n",
    "                j = nxt[j]\n",
    "        return nxt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if not t:\n",
    "            return True\n",
    "        if not s:\n",
    "            return False\n",
    "        no=[]\n",
    "        queue=[s]\n",
    "        while queue:\n",
    "            nq=[]\n",
    "            for node in queue:\n",
    "                if not node:\n",
    "                    continue\n",
    "                if node.val==t.val:\n",
    "                    no.append(node)\n",
    "                nq.append(node.left)\n",
    "                nq.append(node.right)\n",
    "            queue=nq\n",
    "        q=[t]\n",
    "        layq=[]\n",
    "        while q:\n",
    "            nq=[]\n",
    "            for node in q:\n",
    "                if not node:\n",
    "                    layq.append(None)\n",
    "                    continue\n",
    "                nq.append(node.left)\n",
    "                nq.append(node.right)\n",
    "                layq.append(node.val)\n",
    "            q=nq\n",
    "        for nodea in no: \n",
    "            p=[nodea]\n",
    "            layp=[]\n",
    "            while p:\n",
    "                np=[]\n",
    "                for node in p:\n",
    "                    if not node:\n",
    "                        layp.append(None)\n",
    "                        continue\n",
    "                    np.append(node.left)\n",
    "                    np.append(node.right)\n",
    "                    layp.append(node.val)\n",
    "                p=np\n",
    "            if layp==layq:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        stack = [s]\n",
    "        while(stack):\n",
    "            node = stack.pop()\n",
    "            if node.val == t.val and self.judge_equal(node,t):\n",
    "                return True\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        return False\n",
    "\n",
    "    def judge_equal(self, s, t):\n",
    "        stack_s = [s]\n",
    "        stack_t = [t]\n",
    "        while stack_s and stack_t:\n",
    "            node_s = stack_s.pop()\n",
    "            node_t = stack_t.pop()\n",
    "            if node_s.val != node_t.val:\n",
    "                return False\n",
    "            if node_s.left and not node_t.left:\n",
    "                return False\n",
    "            if not node_s.left and node_t.left:\n",
    "                return False\n",
    "            if node_s.right and not node_t.right:\n",
    "                return False\n",
    "            if not node_s.right and node_t.right:\n",
    "                return False\n",
    "            if node_s.left and node_t.left:\n",
    "                stack_s.append(node_s.left)\n",
    "                stack_t.append(node_t.left)\n",
    "            if node_s.right and node_t.right:\n",
    "                stack_s.append(node_s.right)\n",
    "                stack_t.append(node_t.right)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if s is None:\n",
    "            return s == t\n",
    "        Que = collections.deque([s])\n",
    "        while Que:\n",
    "            level = len(Que)\n",
    "            for i in range(level):\n",
    "                curnode = Que.popleft()\n",
    "                ans = self.issame(curnode,t)\n",
    "                if ans == True:\n",
    "                    return True\n",
    "                if curnode.left is not None:\n",
    "                    Que.append(curnode.left)\n",
    "                if curnode.right is not None:\n",
    "                    Que.append(curnode.right)\n",
    "        return False\n",
    "\n",
    "    def issame(self,subtree,t):\n",
    "        Que1 = collections.deque([subtree])\n",
    "        Que2 = collections.deque([t])\n",
    "        while(Que1):\n",
    "            level = len(Que1)\n",
    "            for i in range(level):\n",
    "                curnode1 = Que1.popleft()\n",
    "                curnode2 = Que2.popleft()\n",
    "                if curnode1.val != curnode2.val:\n",
    "                    return False\n",
    "                if curnode1.left is not None and curnode2.left is not None:\n",
    "                    Que1.append(curnode1.left)\n",
    "                    Que2.append(curnode2.left)\n",
    "                elif curnode1.left is None and curnode2.left is None:\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "\n",
    "                if curnode1.right is not None and curnode2.right is not None:\n",
    "                    Que1.append(curnode1.right)\n",
    "                    Que2.append(curnode2.right)\n",
    "                elif curnode1.right is None and curnode2.right is None:\n",
    "                    pass\n",
    "                else:\n",
    "                    return False\n",
    "        if len(Que2) == 0:\n",
    "            return True\n",
    "        else:\n",
    "            return False                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# class Solution:\n",
    "#     def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "#         if not t: return True\n",
    "#         if not s: return False\n",
    "\n",
    "#         return self.isSame(s,t) or self.isSubtree(s.left,t) or self.isSubtree(s.right,t)\n",
    "    \n",
    "#     def isSame(self,s,t):\n",
    "#         if not s and not t: return True\n",
    "#         if not s or not t: return False\n",
    "#         if s.val != t.val: return False\n",
    "#         return self.isSame(s.left,t.left) and self.isSame(s.right,t.right)\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        ss = self.preorder(s)\n",
    "        st = self.preorder(t)\n",
    "        print(st,ss)\n",
    "        return st in ss\n",
    "        \n",
    "    def preorder(self,root):\n",
    "        stack,output = [root],\"\"\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node: \n",
    "                output += '#'+str(node.val)\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.left)\n",
    "            else: output += '*'\n",
    "\n",
    "        return output\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        def dfs(S, T):\n",
    "            if not T and not S:\n",
    "                return True\n",
    "            if not S or not T:\n",
    "                return False\n",
    "            if S.val != T.val:\n",
    "                return False \n",
    "            return dfs(S.left, T.left) and dfs(S.right, T.right)\n",
    "        queue = deque([s])\n",
    "        while(queue):\n",
    "            n = len(queue)\n",
    "            for _ in range(n):\n",
    "                node = queue.popleft()\n",
    "                if node.val == t.val:\n",
    "                    if dfs(node, t):\n",
    "                        return True\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)\n",
    "\n",
    "\n",
    "    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return self.isSameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)\n",
    "\n",
    "\n",
    "    def isSameTree(self, s: TreeNode, t: TreeNode) -> bool:\n",
    "        if not s and not t:\n",
    "            return True\n",
    "        if not s or not t:\n",
    "            return False\n",
    "        return s.val == t.val and self.isSameTree(s.left, t.left) and self.isSameTree(s.right, t.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:\n",
    "        def issame(noder,subRoot)->bool:\n",
    "        #然后类似比较镜像方式 从第二个节点开始\n",
    "        #用队列\n",
    "            queue =deque([noder,subRoot])\n",
    "            while queue:\n",
    "                leftnoder = queue.popleft()\n",
    "                righnoder = queue.popleft()\n",
    "                if not leftnoder and not righnoder:continue\n",
    "                if not leftnoder or not righnoder or leftnoder.val != righnoder.val:return False\n",
    "                queue.append(leftnoder.left)\n",
    "                queue.append(righnoder.left)\n",
    "                queue.append(leftnoder.right)\n",
    "                queue.append(righnoder.right)   \n",
    "            return True\n",
    "\n",
    "        #首先层序寻找 根节点的位置\n",
    "        queue= deque([root])\n",
    "        while queue:\n",
    "            noder = queue.popleft()\n",
    "            if noder.val == subRoot.val:\n",
    "                if issame(noder,subRoot):return True\n",
    "            if noder.left: queue.append(noder.left)\n",
    "            if noder.right:queue.append(noder.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        stack=[root]\n",
    "\n",
    "        while stack:\n",
    "            cur=stack.pop() \n",
    "            if cur.right:\n",
    "                stack.append(cur.right)\n",
    "            if cur.left:\n",
    "                stack.append(cur.left)\n",
    "            if cur.val==subRoot.val:\n",
    "                que=deque()\n",
    "                que.append(cur)\n",
    "                que.append(subRoot)\n",
    "                while que:\n",
    "                    cur1=que.popleft()\n",
    "                    cur2=que.popleft()\n",
    "                    if not cur1 and not cur2:\n",
    "                        continue\n",
    "                    elif cur1 and cur2 and cur1.val==cur2.val:\n",
    "                        pass\n",
    "                    else:\n",
    "                        break\n",
    "                    que.append(cur1.left)\n",
    "                    que.append(cur2.left)\n",
    "                    que.append(cur1.right)\n",
    "                    que.append(cur2.right)\n",
    "                else:\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    #先判断两个子树是否相等的方法\n",
    "    def isSameTree(self, p, q) -> bool:\n",
    "        #队列\n",
    "        from collections import deque\n",
    "        que = deque([p, q])\n",
    "\n",
    "        while que:\n",
    "            node1 = que.popleft()\n",
    "            node2 = que.popleft()\n",
    "            #该对节点均为空，达标，继续后续节点判断\n",
    "            if not node1 and not node2: continue\n",
    "            #至少一个节点不为空\n",
    "            if not node1 or not node2 or node1.val != node2.val: return False\n",
    "            #添加下一层子节点\n",
    "            que.append(node1.left)\n",
    "            que.append(node2.left)\n",
    "\n",
    "            que.append(node1.right)\n",
    "            que.append(node2.right)\n",
    "        return True\n",
    "    #遍历root数中的节点，看是否有与subroot相等的子树（遍历+对比）\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        #利用前序的栈的迭代方法遍历节点\n",
    "        st = [root]\n",
    "        while st:\n",
    "            cur = st.pop()\n",
    "            if self.isSameTree(subRoot, cur): return True\n",
    "\n",
    "            if cur.right:\n",
    "                st.append(cur.right)\n",
    "            if cur.left:\n",
    "                st.append(cur.left)\n",
    "        \n",
    "        return False\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        def compare(root, Root):\n",
    "            if not root and not Root:\n",
    "                return False\n",
    "            \n",
    "            stack = []\n",
    "            stack.append(root)\n",
    "            stack.append(Root)\n",
    "\n",
    "            while stack:\n",
    "                left = stack.pop()\n",
    "                right = stack.pop()\n",
    "                if not left and not right:\n",
    "                    continue\n",
    "                if not left or not right or left.val != right.val:\n",
    "                    return False\n",
    "                \n",
    "                stack.append(left.left)\n",
    "                stack.append(right.left)\n",
    "                stack.append(left.right)\n",
    "                stack.append(right.right)\n",
    "            \n",
    "            return True\n",
    "\n",
    "\n",
    "        results = []\n",
    "        if not root:\n",
    "            return results\n",
    "        \n",
    "        from collections import deque\n",
    "        que = deque([root])\n",
    "\n",
    "        while que:\n",
    "            size = len(que)\n",
    "            result = []\n",
    "            for _ in range(size):\n",
    "                cur = que.popleft()\n",
    "                result.append(cur.val)\n",
    "                if cur.val == subRoot.val:\n",
    "                    if compare(cur, subRoot) == True:\n",
    "                        que = []\n",
    "                        break\n",
    "\n",
    "                if cur.left:\n",
    "                    que.append(cur.left)\n",
    "                if cur.right:\n",
    "                    que.append(cur.right)\n",
    "                \n",
    "            results.append(result)\n",
    "        \n",
    "        \n",
    "        return compare(cur, subRoot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        # 1.递归法\n",
    "        def compare(a, b):\n",
    "            if a == None and b == None: return True\n",
    "            elif a == None and b != None: return False\n",
    "            elif a != None and b ==None: return False\n",
    "            elif a.val != b.val: return False\n",
    "            left = compare(a.left, b.left)\n",
    "            right = compare(a.right, b.right)\n",
    "            return left and right\n",
    "        que = deque()\n",
    "        if root : que.append(root)\n",
    "        while que:\n",
    "            x = que.popleft()\n",
    "            if x.val == subRoot.val:\n",
    "                res = compare(x, subRoot)\n",
    "                if res: return res\n",
    "            if x.left: que.append(x.left)\n",
    "            if x.right: que.append(x.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(\r\n",
    "        self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None\r\n",
    "    ) -> None:\r\n",
    "        self.val = val\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def isSubtree(self, root: TreeNode | None, subRoot: TreeNode | None) -> bool:\r\n",
    "        def is_same_tree(tree1: TreeNode | None, tree2: TreeNode | None) -> bool:\r\n",
    "            queue: collections.deque[TreeNode | None] = collections.deque(\r\n",
    "                [tree1, tree2]\r\n",
    "            )\r\n",
    "\r\n",
    "            while queue:\r\n",
    "                cur_tree1 = queue.popleft()\r\n",
    "                cur_tree2 = queue.popleft()\r\n",
    "\r\n",
    "                if cur_tree1 is None or cur_tree2 is None:\r\n",
    "                    if cur_tree1 is None and cur_tree2 is None:\r\n",
    "                        continue\r\n",
    "                    return False\r\n",
    "\r\n",
    "                if cur_tree1.val != cur_tree2.val:\r\n",
    "                    return False\r\n",
    "\r\n",
    "                queue.append(cur_tree1.left)\r\n",
    "                queue.append(cur_tree2.left)\r\n",
    "                queue.append(cur_tree1.right)\r\n",
    "                queue.append(cur_tree2.right)\r\n",
    "\r\n",
    "            return True\r\n",
    "\r\n",
    "        if root is None:\r\n",
    "            return False\r\n",
    "\r\n",
    "        if is_same_tree(root, subRoot):\r\n",
    "            return True\r\n",
    "\r\n",
    "        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    # 【迭代法】\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        flag = False\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            if flag == False and cur.val == subRoot.val:\n",
    "                # 从这里开始迭代遍历，此时是否存在相同子树部分\n",
    "                new_queue = collections.deque()\n",
    "                new_queue.append(cur)\n",
    "                new_queue.append(subRoot)\n",
    "                while new_queue:\n",
    "                    leftNode = new_queue.popleft()\n",
    "                    rightNode = new_queue.popleft()\n",
    "                    if leftNode == None and rightNode == None:\n",
    "                        continue\n",
    "                    if leftNode == None or rightNode == None or leftNode.val != rightNode.val:\n",
    "                        flag = False\n",
    "                        break\n",
    "                    # 此时，左右节点的数值不为空\n",
    "                    new_queue.append(leftNode.left)\n",
    "                    new_queue.append(rightNode.left)\n",
    "                    new_queue.append(leftNode.right)\n",
    "                    new_queue.append(rightNode.right)\n",
    "                    flag = True\n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "        return flag\n",
    "            \n",
    "            \n",
    "\n",
    "    # 【递归法】\n",
    "    # def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "    #     flag = False\n",
    "    #     queue = collections.deque()\n",
    "    #     queue.append(root)\n",
    "    #     while queue:\n",
    "    #         cur = queue.popleft()\n",
    "    #         if flag == False and cur.val == subRoot.val:\n",
    "    #             flag = self.helper(cur, subRoot)\n",
    "    #         if cur.left:\n",
    "    #             queue.append(cur.left)\n",
    "    #         if cur.right:\n",
    "    #             queue.append(cur.right)\n",
    "    #     return flag\n",
    "    \n",
    "    # def helper(self, left, right):\n",
    "    #     # 1、终止条件\n",
    "    #     if left == None and right != None:\n",
    "    #         return False\n",
    "    #     elif left != None and right == None:\n",
    "    #         return False\n",
    "    #     elif left == None and right == None:\n",
    "    #         return True\n",
    "    #     elif left.val != right.val:\n",
    "    #         return False\n",
    "    #     # 2、下面就是left的val==right的val的情况\n",
    "    #     left_flag = self.helper(left.left, right.left)\n",
    "    #     right_flag = self.helper(left.right, right.right)\n",
    "    #     # 3、返回结束值\n",
    "    #     return left_flag and right_flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        tmp = [root]\n",
    "        while tmp:\n",
    "            t = tmp.pop(0)\n",
    "            if t and t.val == subRoot.val:\n",
    "                f = [t,subRoot]\n",
    "                flag = 0\n",
    "                while f:\n",
    "                    a = f.pop(0)\n",
    "                    s = f.pop(0)\n",
    "                    if (a and not s) or (not a and s):\n",
    "                        flag = 1\n",
    "                        break\n",
    "                    if a and s:\n",
    "                        if a.val != s.val:\n",
    "                            flag = 1\n",
    "                            break\n",
    "                        f.append(a.left)\n",
    "                        f.append(s.left)\n",
    "                        f.append(a.right)\n",
    "                        f.append(s.right)\n",
    "                if flag == 0:\n",
    "                    return True\n",
    "            if t:\n",
    "                tmp.append(t.left)\n",
    "                tmp.append(t.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        def f(a, b):\n",
    "            stack = [a, b]\n",
    "            while stack:\n",
    "                x = stack.pop()\n",
    "                y = stack.pop()\n",
    "                if (not x and y) or (x and not y):\n",
    "                    return False\n",
    "                elif x and y:\n",
    "                    if x.val != y.val:\n",
    "                        return False\n",
    "                    stack.append(x.left)\n",
    "                    stack.append(y.left)\n",
    "                    stack.append(x.right)\n",
    "                    stack.append(y.right)\n",
    "            return True\n",
    "\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            x = stack.pop()\n",
    "            if x.val == subRoot.val and f(x, subRoot):\n",
    "                return True\n",
    "            if x.left:\n",
    "                stack.append(x.left)\n",
    "            if x.right:\n",
    "                stack.append(x.right)\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        if not root or not subRoot:\n",
    "            return False\n",
    "        \n",
    "        myqueue = [root]\n",
    "        while myqueue:\n",
    "            nodelevel_num = len(myqueue)\n",
    "            for _ in range(nodelevel_num):\n",
    "                this_root = myqueue.pop(0)\n",
    "                if this_root.left:\n",
    "                    myqueue.append(this_root.left)\n",
    "                if this_root.right:\n",
    "                    myqueue.append(this_root.right)\n",
    "                \n",
    "                if this_root.val == subRoot.val:\n",
    "                    res = self.cmp_tree(this_root, subRoot)\n",
    "                    if res:\n",
    "                        return True\n",
    "        \n",
    "        return False\n",
    "    \n",
    "    def cmp_tree(self, root1, root2):\n",
    "        if not root1 and root2:\n",
    "            return False\n",
    "        elif not root2 and root1:\n",
    "            return False\n",
    "        elif not root2 and not root1:\n",
    "            return True\n",
    "        elif root2.val != root1.val:\n",
    "            return False\n",
    "        \n",
    "        cmp1 = self.cmp_tree(root1.left, root2.left)\n",
    "        cmp2 = self.cmp_tree(root1.right, root2.right)\n",
    "\n",
    "        res = cmp1 & cmp2\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        if root is None  and subRoot is None:\n",
    "            return True\n",
    "        if root is None or subRoot is None:\n",
    "            return False\n",
    "        return self.isSameTree(root, subRoot) or self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) \n",
    "        # attentiion\n",
    "        \n",
    "\n",
    "    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:\n",
    "        if p is None and q is None:\n",
    "            return True\n",
    "        if p is None or q is None:\n",
    "            return False\n",
    "        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        if not root and not subRoot:\n",
    "            return True\n",
    "        if not root or not subRoot:\n",
    "            return False\n",
    "\n",
    "\n",
    "        def isSameTree(big, small):\n",
    "            if not big and not small:\n",
    "                return True\n",
    "            if not big or not small:\n",
    "                return False\n",
    "            if big.val != small.val:\n",
    "                return False\n",
    "            return isSameTree(big.left, small.left) and isSameTree(big.right, small.right)\n",
    "\n",
    "        return isSameTree(root, subRoot) or self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:\n",
    "        if not subRoot: return True\n",
    "        if not root: return False\n",
    "        if self.isSameTree(root,subRoot): return True\n",
    "        return self.isSubtree(root.left,subRoot) or self.isSubtree(root.right,subRoot)\n",
    "\n",
    "    \n",
    "\n",
    "    def isSameTree(self,root,subtree):\n",
    "        if not root and not subtree:\n",
    "            return True\n",
    "        if not root or not subtree:\n",
    "            return False\n",
    "        return root.val == subtree.val and self.isSameTree(root.left,subtree.left) and self.isSameTree(root.right,subtree.right)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
